package offerv1;

import leetcodev1.链表.Solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Offer38 {
    List<String> list;

    public String[] permutation(String s) {
        if (s == null || s.length() == 0) {
            return new String[]{};
        }

        char[] chars = s.toCharArray();
        int n = chars.length;
        boolean[] visited = new boolean[n];
        list = new ArrayList<>();

        Arrays.sort(chars);

        helper(s, n, 0, new StringBuffer(), visited);
        int size = list.size();
        String[] ans = new String[size];
        for (int i = 0; i < size; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    private void helper(String s, int n, int index, StringBuffer router, boolean[] visited) {
        if (index == n) {
            list.add(router.toString());
            return;
        }

        helper(s, n, index + 1, router, visited);
        if (index == 0 || (index > 1 && s.charAt(index) != s.charAt(index - 1)) || (visited[index - 1])) {
            visited[index] = true;
            router.append(s.charAt(index));
            helper(s, n, index + 1, router, visited);
            router.deleteCharAt(router.length() - 1);
            visited[index] = false;
        }
    }
}

class Answer{
    List<String> rec;
    boolean[] vis;

    public String[] permutation(String s) {
        int n = s.length();
        rec = new ArrayList<String>();
        vis = new boolean[n];
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        StringBuffer perm = new StringBuffer();
        backtrack(arr, 0, n, perm);
        int size = rec.size();
        String[] recArr = new String[size];
        for (int i = 0; i < size; i++) {
            recArr[i] = rec.get(i);
        }
        return recArr;
    }

    public void backtrack(char[] arr, int i, int n, StringBuffer perm) {
        if (i == n) {
            rec.add(perm.toString());
            return;
        }
        for (int j = 0; j < n; j++) {
            if (vis[j] || (j > 0 && !vis[j - 1] && arr[j - 1] == arr[j])) {
                continue;
            }
            vis[j] = true;
            perm.append(arr[j]);
            backtrack(arr, i + 1, n, perm);
            perm.deleteCharAt(perm.length() - 1);
            vis[j] = false;
        }
    }
}
